/**
 * 桶排序
 * 算法思路：找出最大值和最小值，划分n个不同数值范围的桶，将各个值分到各自的桶，桶内插入排序，然后合并桶，最终得到排好序的数组
 * 算法时间复杂度：O(n2)
 * 算法空间复杂度：O(1)
 */
//这个数组下，容易出现 idx 为 undefined
// var innerArr = [577, 615, 553, 740, 748, 631, 68, 201, 76, 460, 653, 289, 89, 236, 888, 257, 3, 623, 313, 336];
// var innerArr = [677, 494, 956, 44, 857, 411, 377, 652, 842, 179, 801, 448, 184, 573, 892, 715, 654, 582, 877, 329];
//主要是固定桶数目，每个桶中数据的条数是不定的
export default function (pararr) {
    if (!Array.isArray(pararr) || pararr.length < 2) {
        return;
    }
    let arr = [].concat(pararr);
    
    //最大最小数
    let minIdx = 0;
    let maxIdx = 0;

    //默认有4个桶，因为数组变长，所以给个基数5，通过这个基数来划分桶的数目
    let base_size = 5;
    let bucket_count = arr.length/base_size;
    // console.log(`bucket_count:${bucket_count}`);
    for(let i = 0;i<arr.length-1;i++){
        //表示最小值的索引起始位置
        if(arr[minIdx]>arr[i+1]){
            minIdx = i+1;
        }
        if(arr[maxIdx]<arr[i+1]){
            maxIdx = i+1;
        }
    }

    //每个桶对应一个数组，数组长度不定，仅值在一定范围
    let buckets = new Array(bucket_count);
    for(let i=0;i<buckets.length;i++){
        buckets[i] = [];
    }
    // console.log('buckets:');
    // console.log(buckets);
    console.log(`max:${arr[maxIdx]}`);
    console.log(`min:${arr[minIdx]}`);
    //均分数据的范围跨度： arr[minIdx] - (arr[minIdx]+gap)
    let gap = Math.ceil((arr[maxIdx]-arr[minIdx])/bucket_count);
    console.log(`gap:${gap}`);

    //分配数据到对应的桶中
    for(let i=0; i<arr.length; i++){
        //@todo 偶尔idx 为 undefined ，何解？
        //@todo 刚好均分的话，数据刚好被整除
        let idx = Math.floor((arr[i]-arr[minIdx])/gap);
        idx = idx>=bucket_count?(bucket_count-1):idx;
        // console.log(`i: ${i},idx: ${idx}`);
        buckets[idx].push(arr[i]);
    }
    console.log(buckets);

    return arr;
}